package 链表;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * @author 会玩的洋洋
 *
 */
public class _19_删除链表的倒数第N个结点 {
	
	/**
	 * 栈
	 * @param head
	 * @param n
	 * @return
	 */
	public ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
        
        for (int i = 0; i < n; i++) {
			stack.pop();
		}
        
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
	
	/**
	 * 快慢指针
	 * @param head
	 * @param n
	 * @return
	 */
	public ListNode removeNthFromEnd2(ListNode head, int n) {
		ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        
        for (int i = 0; i < n; i++) {
			first = first.next;
		}
        
        while (first != null) {
			first = first.next;
			second = second.next;
		}
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
	
	/**
	 * 两次扫描  先遍历出size，然后选取倒数第n个节点的前一个，再将节点的下一个指向目标节点的下一个，完成删除
	 * 如果size - n是0，则意思为将头部删除。
	 * @param head
	 * @param n
	 * @return
	 */
	public ListNode removeNthFromEnd(ListNode head, int n) {
		int size = 0;
        ListNode tail = head;
        while(tail != null) {
            size++;
            tail = tail.next;
        }
        if(size == 1 || size - n == 0) {
            head = head.next;
        }else {
            tail = head;
            for (int i = 1; i < size - n; i++) {
                tail = tail.next;
            }
            tail.next = tail.next.next;
        }
        return head;
    }
	
}
